package 力扣;

import java.util.*;
import java.util.logging.Handler;

public class leetcode106 {
    public static void main(String[] args) {
        buildTreeInt(new int[]{1,2,3},new int[]{3,2,1});
    }
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        List<Integer> in=new ArrayList<>();
        List<Integer> pos=new ArrayList<>();
        for (int i = 0; i < inorder.length; i++) {
            in.add(inorder[i] );
            pos.add(postorder[i]);
        }
        ToATree(root,in,pos);
        return root;
    }
    public static TreeNode buildTreeInt(int[] inorder, int[] postorder) {
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        int inleft = 0;
        int inright = inorder.length -1;
        int posleft = 0;
        int posright = inorder.length - 1;

        //
        ToATreeInt(root,inorder,postorder,inleft,inright,posleft,posright);
        return root;
    }

    private static void ToATreeInt(TreeNode root, int[] inorder, int[] postorder, int inleft, int inright, int posleft, int posright) {
        // 递归结束条件
        if(inleft == inright) return;
        int left = 1;
        int right = 1;
        int inRootIndex = 0;
        int posRootIndex = posright;

        for( int i = inleft; i<=inright; i++){
            if(inorder[i] == root.val){
                inRootIndex = i;
                break;
            }
        }

        if (inRootIndex == inleft) left=0;
        if (inRootIndex == inright) right=0;

        TreeNode rootleft = null;
        TreeNode rootright = null;
        if(right == 1){
            rootright = new TreeNode(postorder[posRootIndex-1]);
        }
        // posIndex定义为 root节点左节点在序列的下一个遍历节点
        int posIndex = 0;
        if(left == 1) {
            if(right == 1){
                int rightLength =inright - inRootIndex;
                posIndex = posRootIndex - rightLength;
            }
            else {
                posIndex = posRootIndex;
            }
            rootleft =new TreeNode(postorder[posIndex - 1]);
        }

        if(rootleft!=null){
            root.left = rootleft;
            if(right == 1){
                ToATreeInt(root.left,inorder,postorder,inleft,inRootIndex-1,posleft,posIndex-1);
            }else {
                ToATreeInt(root.left,inorder,postorder,inleft,inRootIndex-1,posleft,posright-1);
            }
        }
        if(rootright!=null){
            root.right=rootright;
            if(left==1){
                ToATreeInt(root.right,inorder,postorder,inRootIndex+1,inright,posIndex,posRootIndex-1);
            }
            else {
                ToATreeInt(root.right,inorder,postorder,inRootIndex+1,inright,posleft,posRootIndex-1);
            }
        }


    }


    private  static void ToATree(TreeNode root, List<Integer> in, List<Integer> pos) {
        int left = 0;
        int right = 0;
        // 获取 root 在 前序数组的指针
        int rootInIndex = in.indexOf(root.val);
        int rootPosIndex = pos.indexOf(root.val);
        // 获取右子树长度
        int rightlength = in.size() - rootInIndex -1;
        // 左子树
        if(rootInIndex == 0) left=-1;
        // 右子树
        if(rootInIndex == in.size()-1) right=-1;
        if(left==-1&&right==-1) return;

        TreeNode rootright = null;
        TreeNode rootleft = null;
        // 存在右子树
        if(right == 0){
            rootright = new TreeNode(pos.get(pos.size()-2));
        }
        // 存在左子树
        // posIndex 右子树的第一个节点 也可能没有
        int posIndex = 0;
        if(left == 0){
            // 如果存在右子树
            if(right == 0){
                posIndex = rootPosIndex - rightlength;
            }
            // 如果不存在右子树
            else {
                posIndex = pos.size() - 1;
            }
            rootleft = new TreeNode(pos.get(posIndex - 1));
        }
        if(rootleft!=null){
            root.left = rootleft;
            if(right==0){
                ToATree(root.left,in.subList(0,rootInIndex),pos.subList(0,posIndex));
            }
            else {
                ToATree(root.left,in.subList(0,rootInIndex),pos.subList(0,rootPosIndex));
            }
        }
        if(rootright!=null){
            root.right = rootright;
            if(left==0){
                ToATree(root.right,in.subList(rootInIndex+1,in.size()),pos.subList(posIndex,pos.size()-1));
            }
            else {
                ToATree(root.right,in.subList(rootInIndex+1,in.size()),pos.subList(0,pos.size()-1));
            }
        }

    }
}
